package 面试超级高频.LRU纯净版;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

import static MyUtils.MHUtils.*;
import static MyUtils.MHMoban.*;


public class LRU纯净版 {

    class DoubleNode{
        int key,val;
        DoubleNode prep,next;
        DoubleNode(int k,int v){
            key=k; val=v;
        }
    }
    class LRUCache {
        Map<Integer, DoubleNode> map = new HashMap<>();
        DoubleNode dm1, dm2;
        int curSize=0;
        int maxSize;
        public LRUCache(int maxSize) {
            this.maxSize=maxSize;
            dm1 =new DoubleNode(-1,-1);dm2 =new DoubleNode(-1,-1);
            dm1.next= dm2;dm2.prep= dm1;
        }

        /**
         * 链表工具
         */
        void list_addRight(DoubleNode node){
            curSize++;
            DoubleNode t = dm2.prep;
            //左2
            t.next=node;
            node.prep=t;
            //右2
            node.next=dm2;
            dm2.prep=node;
        }
        void list_delByNode(DoubleNode node){
            curSize--;
            //放心
            DoubleNode lf = node.prep, rt=node.next;
            lf.next=rt;
            rt.prep=lf;
        }

        /**
         * 题干接口
         */
        public void put(int key, int val) {
            //无key
            if(map.containsKey(key)) {
                DoubleNode node = map.get(key);
                list_delByNode(node);
                DoubleNode newNode = new DoubleNode(key, val);
                list_addRight(newNode);
                map.put(key, newNode);
            }else{
                //不满
                if(curSize<maxSize){
                    DoubleNode node = new DoubleNode(key,val);
                    list_addRight(node);
                    map.put(key,node);
                }
                else{
                    //删左
                    DoubleNode head = dm1.next;
                    int head_key = head.key;
                    list_delByNode(head);
                    map.remove(head_key);
                    //插右
                    DoubleNode node = new DoubleNode(key, val);
                    list_addRight(node);
                    map.put(key, node);
                }
            }
        }
        public int get(int key) {
            if(!map.containsKey(key)){
                return -1;
            }else{
                DoubleNode node = map.get(key);
                list_delByNode(node);
                list_addRight(node);
                return node.val;
            }
        }
    }
}
